package com.kabuda.zhugehot200_review;

/**
 * @author kabuda
 * @date 2025-03-18 21:23
 * @description
 */
public class t547_省份数量 {
    public static void main(String[] args) {
        int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        System.out.println(new t547_省份数量().findCircleNum(isConnected));

    }

    public int findCircleNum(int[][] isConnected) {
        int length = isConnected.length;
        int provinces = 0;
        boolean[] isVisited = new boolean[length];
        for (int i = 0; i < length; i++) {
            if (!isVisited[i]) {
                provinces++;
                dfs(isConnected, isVisited, i);
            }
        }
        return provinces;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int i) {
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isConnected, visited, j);
            }
        }
    }

}
